W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Mrówka ma obejść wszystkie pola szachownicy poza polami zabronionymi — każde pole dokładnie jeden raz. Obchodzenie musi się zacząć w polu startowym leżącym w lewym górnym rogu i zakończyć na polu leżącym na brzegu szachownicy (mrówka na końcu opuszcza szachownicę). Zakładamy, że pole startowe nie jest zabronione. W jednym kroku mrówka może przejść do jednego z co najwyżej czterech sąsiednich pól szachownicy (w górę, dół, lewo lub prawo).
Mrówka obchodzi szachownicę w sposób w pewnym sensie rekurencyjny: aby obejść kwadrat dzieli go na cztery części (rekurencyjne ćwiartki) o rozmiarach , a następnie obchodzi każdą z nich, to znaczy, jeżeli mrówka wejdzie do jednej z ćwiartek, to może z niej wyjść dopiero wtedy, gdy obejdzie wszystkie nie zabronione pola w tej ćwiartce.
Rysunek przedstawia dwie trasy rekurencyjnej wędrówki mrówki na szachownicy o rozmiarach , od pola startowego do pola leżącego odpowiednio na górnym oraz lewym brzegu szachownicy.
Napisz program, który:
Uwaga: każde z czterech pól narożnych należy do dwóch brzegów szachownicy.
W pierwszym wierszu standardowego wejścia jest zapisana liczba całkowita dodatnia , . W drugim wierszu jest zapisana liczba pól zabronionych , .
W każdym z kolejnych wierszy jest zapisana para liczb całkowitych nieujemnych oddzielonych pojedynczym odstępem, są to dwie współrzędne: numer wiersza oraz numer kolumny odpowiedniego zabronionego pola. Wiersze szachownicy numerujemy od góry w dół, a kolumny od lewej do prawej, od do .
W każdym z czterech kolejnych wierszy standardowego wyjścia należy zapisać dwie liczby całkowite nieujemne oddzielone pojedynczym odstępem — współrzędne (numer wiersza i numer kolumny) odpowiedniego końcowego pola rekurencyjnej trasy mrówki leżącego na: górnym, prawym, dolnym oraz lewym brzegu szachownicy (w takiej kolejności) lub jedno słowo NIE, jeśli takiego pola nie ma.
Dla danych wejściowych:
3 17 2 0 1 0 3 0 6 0 7 0 6 1 7 1 6 2 7 2 6 3 7 3 0 2 0 3 0 6 0 7 1 6 1 7
poprawną odpowiedzią jest:
0 4 NIE NIE 4 0
Autor zadania: Wojciech Rytter.